We consider the problem of proper learning a Boolean Halfspace with integerweights $\{0,1,\ldots,t\}$ from membership queries only. The best knownalgorithm for this problem is an adaptive algorithm that asks $n^{O(t^5)}$membership queries where the best lower bound for the number of membershipqueries is $n^t$ [Learning Threshold Functions with Small Weights UsingMembership Queries. COLT 1999] In this paper we close this gap and give an adaptive proper learningalgorithm with two rounds that asks $n^{O(t)}$ membership queries. We also givea non-adaptive proper learning algorithm that asks $n^{O(t^3)}$ membershipqueries.
展开▼
机译：我们考虑仅从成员资格查询中正确学习具有整数权重$ \ {0,1，\ ldots，t \} $的布尔半空间的问题。此问题的最佳已知算法是一种自适应算法，该算法会询问$ n ^ {O（t ^ 5）} $成员资格查询，其中成员资格查询数的最佳下限是$ n ^ t $查询。 [COLT 1999]在本文中，我们弥合了这一差距，并给出了两轮询问$ n ^ {O（t）} $成员资格查询的自适应适当学习算法。我们还给出了一种非自适应的正确学习算法，该算法询问$ n ^ {O（t ^ 3）} $成员资格查询。
展开▼
